package com.yanceysong.codetop.s11_s20;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;


public class S17_Easy_20_有效的括号 {
    /**
     * S17_Easy_20_有效的括号
     * <p>
     * <a href="https://leetcode.cn/problems/valid-parentheses/">...</a>
     * <p>
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     * <p>
     * 有效字符串需满足：
     * 1. 左括号必须用相同类型的右括号闭合。
     * 2. 左括号必须以正确的顺序闭合。
     * 3. 每个右括号都有一个对应的相同类型的左括号。
     * <p>
     * 解题思路：栈（Stack）
     * 1. 括号匹配是栈的经典应用场景。栈具有“后进先出”（LIFO）的特性，非常适合处理配对问题。
     * 2. 创建一个栈，遍历输入的字符串。
     * 3. 如果遇到左括号（'('、'['、'{'），就将其压入栈中。
     * 4. 如果遇到右括号（')'、']'、'}'），则检查栈顶元素：
     * .    a. 如果栈为空，说明没有对应的左括号，字符串无效。
     * .    b. 如果栈顶的左括号与当前右括号不匹配，字符串无效。
     * .    c. 如果匹配，则将栈顶元素弹出（出栈）。
     * 5. 遍历完整个字符串后，如果栈为空，说明所有的括号都已成功匹配，字符串有效；否则，说明有未匹配的左括号，字符串无效。
     * <p>
     * 图解算法 (s = "({[]})"):
     * 1. 遇到 '(':  栈 <- '('
     * 2. 遇到 '{':  栈 <- '(', '{'
     * 3. 遇到 '[':  栈 <- '(', '{', '['
     * 4. 遇到 ']':  栈顶是 '[', 匹配成功。出栈。 栈 -> '(', '{'
     * 5. 遇到 '}':  栈顶是 '{', 匹配成功。出栈。 栈 -> '('
     * 6. 遇到 ')':  栈顶是 '(', 匹配成功。出栈。 栈 -> (空)
     * 遍历结束，栈为空。所以字符串有效。
     * <p>
     * 时间复杂度：O(n)，其中 n 是字符串的长度。我们只需要遍历一次字符串。
     * 空间复杂度：O(n)，在最坏的情况下（例如 "((("），我们需要将所有字符都压入栈中。
     */
    public boolean isValid(String s) {
        // 字符串长度为奇数，肯定无效
        if (s.length() % 2 != 0) {
            return false;
        }

        // 使用 Map 存储括号的配对关系，key 为右括号，value 为左括号
        Map<Character, Character> pairs = new HashMap<>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};

        // Deque 可以作为栈使用，性能比 Stack 好
        Deque<Character> stack = new LinkedList<>();

        for (char ch : s.toCharArray()) {
            if (pairs.containsKey(ch)) { // 如果是右括号
                // 栈为空，或者栈顶的左括号不匹配
                if (stack.isEmpty() || !stack.peek().equals(pairs.get(ch))) {
                    return false;
                }
                stack.pop(); // 匹配成功，出栈
            } else { // 如果是左括号
                stack.push(ch); // 入栈
            }
        }

        // 遍历结束后，栈必须为空才算有效
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        S17_Easy_20_有效的括号 solution = new S17_Easy_20_有效的括号();

        // 测试用例
        String[] testCases = {
                "()",           // true
                "()[]{}",      // true
                "({[]})",      // true
                "(]",          // false
                "([)]",        // false
                "]",          // false
                "[",           // false
                "",             // true (空字符串是有效的)
                "((){}[])"     // true
        };

        boolean[] expectedResults = {
                true, true, true, false, false, false, false, true, true
        };

        for (int i = 0; i < testCases.length; i++) {
            String s = testCases[i];
            boolean expected = expectedResults[i];
            boolean actual = solution.isValid(s);
            System.out.printf("测试: \"%s\" | 预期: %s | 结果: %s | %s%n",
                    s, expected, actual, (expected == actual ? "✅" : "❌"));
        }
    }
}

